1. Field of the Invention
The present invention relates to internetworking systems and in particular to methods and apparatus for managing traffic flow and quality of service in routers and switches.
2. Description of the Related Art
Internetworking encompasses all facets of communications between and among computer networks. Such communications data flow streams may include voice, video, still images, and data traffic. All have widely varying needs in terms of propagation delay (or latency) during transit through the network. Various systems and devices, both in hardware and in software, have attempted to deal with the plethora of data flow requirements present in modern internetworking systems.
A particular problem in internetworking traffic regulation arises from the variety of traffic sources or flows presented to the router/switching device. Referring to FIG. 1, illustrating a high-level schematic view of the operation of a prior art router/switch 100, a number of input flows 110 are presented to the unit. These flows each consist of multiple packets of data in a variety of sizes and presented at a variety of rates. Flows may also be presented in different protocols, such as the Transmission Control Protocol/Internet Protocol (TCP/IP) and the related User Datagram Protocol (UDP), File Transfer Protocol (FTP), Terminal Emulation Protocol (Telnet), and Hypertext Transfer Protocol (HTTP). Other protocols are found in the literature, such as Merilee Ford, et. al., Internetworking Technologies Handbook (Cisco Press 1997) (hereinafter Ford), incorporated herein by reference in its entirety. The packets are buffered in a buffer pool 120, which is typically random access memory (RAM). Buffering is accomplished according to the directives of a controller 130 and a buffer manager 140. The flows are sent to the proper output port 150 by way of a set of output queues 160 and a port scheduler 170. Controller 130, buffer manager 140, and port scheduler 170 are conventionally implemented as one or more high speed microprocessors with associated interface circuitry.
Quality of Service (QoS) is an attribute of the flow in a given data interchange, i.e., a specification placed on the internetworking devices participating in a communications session controlling the timeliness or latency of the communications. Several methods are known in the prior art for configuring QoS in a network, such as the Resource Reservation Protocol (RSVP) described in Chapter 41 of Ford.
One such scheme for ensuring QoS, known as Committed Access Rate (CAR) service, consists of attempting to regulate the traffic within the router or switch connecting multiple networks in the typical internetworking system. Such schemes attempt to provide fair allocation of data throughput capacity (bandwidth) by allocating router buffer and/or queue space according to the type of packets in each flow stream received. A user is, in essence, sold a certain bandwidth, “B.” Flows from that user are not allowed to exceed bandwidth B except when the flows have been consistently less than B for some period of time. Then, and only then, will the switch allow burst traffic (i.e., traffic with bandwidth greater than B) to pass.
Of course, QoS is only useful if there are multiple queues (input and/or output) wherein packets in one queue are given preferential treatment over packets in another queue. In such systems, a method of optimizing queue assignments that allows this differentiated service to be guaranteed (and thus sold to users) is needed.
FIG. 2 illustrates the standard bit configuration for an Internet Protocol packet, including the fields within its header. Flow type, also known as flow classification, information can be found in, for instance, the type of service (TOS) field 210 in the internet protocol (IP) header 200 or in the source address 220 of the received packet. It can also be deduced from the type of packet received; voice being of a higher priority and thus demanding of a larger buffer count than other flows. While dynamic buffer limiting (DBL) is known, current schemes are unable to update their limit values fast enough to keep up with the latest generation of ultra-fast (e.g., Gigabit speed) flows.
As an additional drawback, the use of TOS field 210 is not standardized among internetworking users. Many competing standards, in fact, exist to define how the TOS octet is interpreted.
Examples of competing definitions are found in P. Almquist, Type of Service in the Internet Protocol Suite, Internet Request for Comments (RFC) 1349 (July 1992); D. Eastlake III, Physical Link Security Type of Service, RFC 1455 (May 1993); and K. Nichols, et al., Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers, RFC 2474 (December 1998), all incorporated herein by reference in their entireties. Thus, neither TOS nor source address is a reliable means of identifying flow type at this time.
Source address 220 is a 32-bit value that describes the source of the IP packet. Since the Internet Protocol is connection-less, i.e., data is transmitted onto the network without first establishing an explicit “connection” between sender and receiver, each packet must contain both the full address of the sender and of the recipient. The content and use of the information contained within IP packet header 200 is described in further detail in K. S. Siyan, Inside TCP/IP (New Riders Publishing, 3d ed. 1997) (hereinafter Siyan), incorporated herein by reference in its entirety.
The source address consists of two fields, a network ID and a host ID. The network ID is n bits long (minimum of 8 bits, originally in 8 bit increments, e.g., 8, 16, or 24 bits) and identifies the sending network or “autonomous system” (AS). The autonomous system (AS) is an independently managed network of host computers within an interconnected network of networks. The host ID is (32-n) bits and identifies the particular host computer within the sending AS.
The source address clearly provides an indication of the sender, but, by itself, it does not reveal the priority or required timeliness (i.e., the QoS specified by the sender) for the flow. Indeed, in the modern network, certain flows are actually aggregations of many lower rate flows, each potentially having its own QoS requirement. For example, the Internet backbone carries flows consisting of consolidated traffic from one Internet Service Provider (ISP) to another ISP. Within this aggregated flow are individual packets from multiple discrete flows such as a Voice-over-Internet Protocol (VoIP) call between two users, an HTTP request, and an FTP download. Each packet has its own latency limitation requirement, yet all are within the same ISP-to-ISP aggregated flow. Simply classifying the aggregated flow based on its source address (or AS label) is not sufficient to efficiently allocate switch resources and provide the desired packet level QoS.
A further drawback in the prior art lies in the fact that while all packets within an autonomous system (by definition) use the same TOS field definition, those definitions frequently do not cross AS boundaries. In other words, at the AS-to-AS connection, TOS field meanings are lost.
Thus, in the era of high volume aggregated flows containing packets with numerous divergent QoS requirements, prior art per-flow classification systems are unable to provide the necessary packet-tailored QoS to satisfy users. Such systems are known as “policy” routing schemes for their method of directing resources to flows based on external system administrator decisions on the appropriate flow QoS. Policy routing can define a limited number of custom routing paths for selected packets based on certain criteria (such as source address or physical flow input port). For instance, particular traffic flows, such as VoIP, may be sent over special routes that minimize hop counts and other delay characteristics well-known in the art to ensure high QoS. An example of an element of policy routing is Committed Access Rate (CAR) service, discussed above, wherein three bits in the TOS field 210 are used to identify the packet based on a classification according to certain limited criteria. However, the rules for these policy routing decisions are set a priori (for the most part) by the system administrator and are not flexible and adaptable enough to accommodate the extremely high bandwidth of backbone-level, carrier class (ISP-to-ISP) traffic. Also, mechanisms such as CAR are perceived to be too slow to handle ultra-high bandwidth flows.
What is needed is a method to rapidly and adaptably remap packet header data so that the queuing and forwarding portion of the switch/router can efficiently deliver the packet-wise desired quality of service to ultra-high bandwidth, carrier-class flows.